Modern data storage systems attempt to store data reliably, i.e., store the data in a redundant (encoded) form ensuring that if a small number data items get corrupted (e.g., due to device failures) no information is lost. Data storage systems also attempt to keep all the data readily available for the users, making solutions based on standard error-correcting codes impractical. Designing systems that perform well with respect to these conditions is a challenge.
One solution is to partition the data into small blocks, each of which is then encoded separately. This solution allows efficient random access to information, since one decodes only the portion of data in which one is interested. However, this solution yields poor noise resilience, because when even a single block is completely corrupted, some information is lost. Another solution is to encode all the data into a single codeword of some standard error-correcting code. Such a solution improves the robustness to errors but is not satisfactory, because one needs to look at the whole codeword in order to recover any particular piece of the data.
Another solution is to encode all the data into a single codeword using a locally decodable code. However, conventionally, this solution is not suitable for many applications, since conventional locally decodable codes require a prohibitively large increase in the encoding size compared to the data size.